19. 删除链表的倒数第 N 个结点
题目
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
示例 1:
1 2
| 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
|
示例 2:
1 2
| 输入:head = [1], n = 1 输出:[]
|
示例 3:
1 2
| 输入:head = [1,2], n = 1 输出:[1]
|
题解
使用快慢指针,快指针先走 n + 1步,然后快慢指针一起走,直到快指针的下一个节点为 None,此时,慢指针的下一个元素就是待删除元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next
class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ dummy = ListNode(next=head) fast, slow = dummy, dummy
while n != 0: fast = fast.next n -= 1
while fast.next is not None: fast = fast.next slow = slow.next
slow.next = slow.next.next
return dummy.next
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| type ListNode struct { Val int Next *ListNode }
func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := ListNode{ Next: head, } fast, slow := &dummy, &dummy for n!=0{ fast = fast.Next n -=1 } for fast.Next!=nil{ fast = fast.Next slow = slow.Next } slow.Next = slow.Next.Next return dummy.Next }
|
变体
总结
参考